package com.demo.alg.chapter4分治策略;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**分治思想
 *
分治的思想总的来说就是”大事化小，小事化了”，它将复杂的问题往简单划分，直到划分为可直接解决的问题，再从这个直接可以解决的问题向上聚合，最后解决问题。
从 M 个元素中取出 N 个元素整个问题很复杂，用分治思想就可以理解为：
首先，如果我们已经从 M 中元素取出了一个元素，那么集合中还剩下 M-1 个，需要取的元素就剩下 N-1 个。还不好解决的话，我们假设又从 M-1 中取出了一个元素，集
合中还剩下 M-2 个，需要取的元素只剩下 N-2 个。直到我们可能取了有 M-N+1 次，需要取的元素只剩下一个了，再从剩余集合中取，就是一个简单问题了，很简单，取
法有 M-N+1 种。如果我们解决了这个问题，已经取完最后一次了产生了 M-N+1 种临时集合，再考虑从 M-N+2 个元素中取一个元素呢，又有 M-N+2 种可能。将这些可能
聚合到一块，直到取到了 N 个元素，这个问题也就解决了。
还是从 5 个元素中取 3 个元素的示例：
从 5 个元素中取 3 个元素是一个复杂问题，为了简化它，我们认为已经取出了一个元素，还要再从剩余的 4 个元素中取出 2 个，求解公式为：。从 4 个元素中取出 2 个依
旧不易解决，那我们再假设又取出了一个元素，接下来的问题是如何从 3 个元素中取一个，公式为 。从 3 个元素中取 1 个已经是个简单问题了，有三种可能，再向上追溯，
与四取一、五取一的可能性做乘，从而解决这个问题。代码实现用代码实现如下：

 * @author DELL
 *
 */
public class Combination {

	public static void main(String[] args) {
		List<String> m = Arrays.asList("a", "b", "c", "d", "e");
		Set<Set<String>> combinationAll = new HashSet<>();
		combinationAll.addAll(combination(m, new ArrayList<>(), 3));
		System.out.println(combinationAll);
	}

	private static Set<Set<String>> combination(List<String> remainEle, List<String> tempCollection, int fetchCount) {
		if (fetchCount == 1) {
			Set<Set<String>> eligibleCollections = new HashSet<>();
			for (String ele : remainEle) {
				Set<String> collection = new HashSet<>(tempCollection);
				collection.add(ele);
				eligibleCollections.add(collection);
			}
			return eligibleCollections;
		}
		fetchCount--;
		Set<Set<String>> result = new HashSet<>();
		for (int i = 0; i < remainEle.size(); i++) {
			List<String> collection = new ArrayList<>(tempCollection);
			List<String> tempRemain = new ArrayList<>(remainEle);
			collection.add(tempRemain.remove(i));
			result.addAll(combination(tempRemain, collection, fetchCount));
		}
		return result;
	}

}
